import java.util.ArrayList;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-04-22
 * Time: 9:48
 */

class Point{
    public int x;
    public int y;

    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Solution {
    public int[][] next  = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


    public void solve(char[][] board) {
        List<Point> positions = new ArrayList<>();
        int row = board.length;
        int col = board[0].length;
        // 将周围四条边上的 'O' 位置进行保存, 作为后面的 dfs 的起始位置
        // 这样遍历到的都是没有被包围的位置
        for (int i = 0; i < row; i++) {
            if(board[i][0] == 'O'){
                positions.add(new Point(i, 0));
            }
            if(board[i][col - 1] == 'O'){
                positions.add(new Point(i, col - 1));
            }
        }

        for (int i = 1; i < col-1; i++) {
            if(board[0][i] == 'O'){
                positions.add(new Point(0, i));
            }
            if(board[row - 1][i] == 'O'){
                positions.add(new Point(row - 1, i));
            }
        }
        // 以所有的起点开始遍历
        for (Point point: positions) {
            dfs(board, point.x, point.y, row, col);
        }
        // 被包围的置为 'X'
        // 没有被包围的再修改过来
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(board[i][j] != '0' && board[i][j] != 'X'){
                    board[i][j] = 'X';
                }
                if(board[i][j] == '0'){
                    board[i][j] = 'O';
                }
            }
        }
    }

    public void dfs(char[][] board, int sr, int sc, int row, int col){
        // 将没有被包围的位置置为 '0', 以便与被包围的位置进行区分
        board[sr][sc] = '0';
        for (int i = 0; i < 4; i++) {
            int newR = sr + next[i][0];
            int newC = sc + next[i][1];
            // 只遍历符合条件的
            if(newR < 0 || newR >= row || newC < 0 || newC >= col || board[newR][newC] != 'O'){
                continue;
            }
            dfs(board, newR, newC, row, col);
        }
    }
}
